package 剑指offer.demo2;

//https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?

/**
 * 根据前序与中序遍历递归的确定左右子树构建二叉树
 * 注：1、确定左右子树是边界问题的处理；
 * 2、for循环遍历中序结果时只是查找到pre第一个元素（即树根）对应in中的位置真正的构建过程发生在确定左右子树的过程中
 */
public class 重建二叉树 {
    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        //合法性判断
        if (pre == null || vin == null){
            return null;
        }
        return funHelp(pre , 0 , pre.length - 1 , vin , 0 , vin.length - 1);
    }
    //根据前序遍历与中序遍历和他们的边界构建二叉树
    public TreeNode funHelp (int[] pre , int preStart , int preEnd , int[] in , int inStart , int inEnd){
        //合法性判断，边界合理性
        if (preStart > preEnd || inStart > inEnd){
            return null;
        }
        //创建一个带返回二叉树
        TreeNode root = new TreeNode(pre[preStart]);
        //循环中序遍历的数组找到其前序遍历第一个值（树根）可以将中序数组分成左右半部分；记住for循环知识确定根的过程，构建在左右子树确定时发生,右边界要相等哟
        for (int i = inStart; i <= inEnd; i++) {
            //确定好根的位置（即pre的第一个是根在in中找到所以其左右子树也可以确定好）
            if (in[i] == pre[preStart]){
                //确认左子树，注：因为preStart是树根所以肯定不是左子树，所以其左子树值边界preStart + 1开始到
                //pre右边界：i是从in中查找到的i-inStart的距离就是左子树的长度+preStart就是左子树右边界
                root.left = funHelp(pre , preStart + 1 , preStart + i - inStart , in , inStart , i - 1);
                //确定右子树
                root.right =funHelp(pre , preStart + i - inStart + 1 , preEnd , in , i + 1 , inEnd );
                //左右子树都确定好了，跳出即可
                break;
            }
        }
        return root;
    }
    //题目给定二叉树类
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
